﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmExercise.Introduction
{
    /// <summary>
    /// 归并排序。
    /// 拆分数组再合并
    /// </summary>
    public class MergeSort
    {
        public void Run()
        {
            var random = new Random();
            int[] array = new int[1000];
            for (int n = 0; n < array.Length; n++)
            {
                array[n] = random.Next(1000);
            }
            DoMergeSort(array, 0, array.Length - 1);
            array.ToList().ForEach(i => Console.Write($"{i} "));

        }
        void DoMergeSort(int[] array, int p, int q)
        {
            if (p < q)
            {
                int center = (q - p) / 2;
                DoMergeSort(array, p, p + center);
                DoMergeSort(array, p + center + 1, q);
                DoMerge(array, p, p + center, q);
            }
        }
        void DoMerge(int[] array, int p, int q, int r)
        {
            int n1 = q - p + 1; //前半部分的长度
            int n2 = r - q;//后半部分的长度
            int[] a1 = array.Skip(p).Take(n1).ToArray();
            int[] a2 = array.Skip(q + 1).Take(n2).ToArray();
            int i = 0, j = 0;
            for (int index = p; index <= r; index++)
            {
                if (i == n1 && j != n2)
                {
                    array[index] = a2[j++];
                }
                else if (j == n2 && i != n1)
                {
                    array[index] = a1[i++];
                }
                else if (i < n1 && j < n2)
                {
                    if (a1[i] <= a2[j])
                    {
                        array[index] = a1[i++];
                    }
                    else
                    {
                        array[index] = a2[j++];
                    }
                }
            }
        }
    }
}
